'''
https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/description/
'''
from collections import defaultdict
from typing import List


class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)
        graph = [[] for _ in range(n)]
        for v in range(1, n):
            graph[parent[v]].append(v)

        ans = 0
        def f(u):
            r1, r2 = 0, 0
            for v in graph[u]:
                r = f(v)
                if s[v] != s[u]:
                    if r > r1:
                        r1, r2 = r, r1
                    elif r > r2:
                        r2 = r
            nonlocal ans
            ans = max(ans, r1 + r2 + 1)
            return r1 + 1
        f(0)
        return ans


parent = [-1, 0, 1]
s = "aab"
print(Solution().longestPath(parent, s))
